Парковка имеет n мест, пронумерованных от 1 до n включительно. Парковка открывается
пустой каждое утро и работает на протяжении дня следующим образом. Когда
автомобиль приезжает на парковку, парковщик проверяет, есть ли свободные места.
Если таковых нет, автомобиль ожидает возле въезда до тех пор, пока освободится
какое-то место. Если есть свободное место, или как только оно освобождается,
автомобиль занимает свободное парковочное место. Если есть несколько свободных
парковочных мест, автомобиль занимает место с наименьшим номером. Когда
приезжают парковаться другие автомобили, но уже есть ожидающий автомобиль, они
выстраиваются в очередь на въезде в том порядке, в котором приехали. После
того, как освобождается парковочное место, его занимает первый автомобиль из
очереди (то есть тот, который прибыл парковаться первым).
Стоимость
парковки одного автомобиля в долларах определяется как произведение веса этого
автомобиля в килограммах на тариф его парковочного места. Стоимость парковки
автомобиля не зависит от того, сколько времени этот автомобиль находится на
парковке.
Парковщик знает,
что сегодня на парковку приедет m
автомобилей, и он знает порядок их приезда и отъезда. Помогите ему подсчитать,
сколько долларов он сегодня заработает.
Напишите программу,
которая по заданным тарифам парковочных мест, весам автомобилей и порядку, в
котором автомобили приезжают и уезжают, определяет доход парковки в долларах.
Вход. Первая строка содержит два целых числа
– количество парковочных мест n (1
≤ n ≤ 100) и количество
автомобилей m (1 ≤ m ≤ 2,000), разделенные пробелом.
Следующие n строк
описывают тарифы парковочных мест, s-ая
из этих строк содержит одно целое число rs
(1 ≤ rs ≤ 100)
– тариф парковочного места с номером s
в долларах за килограмм.
Следующие m
строк описывают веса автомобилей. Автомобили пронумерованы в произвольном
порядке от 1 до m включительно, k-ая из этих m строк содержит одно целое число wk (1 ≤ wk
≤ 10,000) – вес автомобиля с номером k
в килограммах.
Следующие 2m
строк описывают приезд и выезд всех автомобилей в хронологическом порядке.
Положительное целое число i
показывает, что автомобиль с номером i
приезжает на парковку. Отрицательное целое число -i показывает, что автомобиль с номером i уезжает с парковки. Никакой автомобиль не выезжает с парковки до
своего приезда, и все автомобили от 1 до m
включительно появятся в этой последовательности строк ровно 2 раза, один раз
как приезжающий, и второй – как выезжающий. К тому же, никакой из автомобилей
не выедет с парковки, пока не займет место на парковке (то есть, никакой
автомобиль не уедет пока стоит в очереди).
Выход. Одно целое число – общее количество
долларов, которое заработает сегодня парковщик.
|
Пример входа |
Пример выхода |
|
3 4 2 3 5 200 100 300 800 3 2 -3 1 4 -4 -2 -1 |
5300 |
структуры
данных
Анализ алгоритма
При помощи
структур данных промоделируем процесс движения автомобилей. Информацию о пустых
парковочных местах будем хранить во множестве s. Таким образом поиск свободной парковки
с наименьшим номером будет производиться за O(log2n). Для каждой машины при помощи
структуры map запомним парковочное место, на которое она была поставлена. При
выезде машины за O(log2n)
можно будет найти номер парковки, которую она освобождает.
Поскольку въезд
и выезд машины из парковки моделируется за O(log2n), то общее время работы алгоритма
составит O(mlog2n).
Реализация алгоритма
Стоимость
парковочных мест заносим в массив price, а веса автомобилей – в массив weight. Во множестве s
будем хранить номера пустых парковочных мест. Таким образом s.begin() будет содержать свободное
парковочное место с наименьшим номером. В отображении mp будем хранить
информацию о машинах, которые поставлены на парковку. Равенство mp[car] = ParkingPlace означает, что
автомобиль с номером car
поставили на парковку номер ParkingPlace.
Очередь машин, ждущих освобождения парковочных мест, храним в очереди d.
int
price[101], weight[2001];
set<int>
s;
map<int,int> mp;
deque<int>
d;
Читаем входные данные.
scanf("%d %d",&n,&m);
Занесем во
множество s список свободных
парковочных мест. Изначально все парковки от 1 до n свободны.
for(i
= 1; i <= n; i++) s.insert(i);
Считываем стоимость парковочных
мест и веса автомобилей.
for(i
= 1; i <= n; i++) scanf("%d",&price[i]);
for(i
= 1; i <= m; i++) scanf("%d",&weight[i]);
Последовательно читаем и обрабатываем команды о приезде и
выезде автомобилей.
for(res
= 0, i = 1; i <= 2 * m; i++)
{
scanf("%d",&car);
Автомобиль
заезжает на парковку.
if (car >
0)
{
Если множество свободных
парковочных мест s не
пусто, то имеется хотя бы одно место куда можно поставить автомобиль.
if
(!s.empty())
{
Присваиваем ParkingPlace наименьший номер свободного
парковочного места.
ParkingPlace = *s.begin();
К результату res прибавляем прибыль парковщика.
res += weight[car] * price[ParkingPlace];
На место s.begin() только что приехала машина.
Отмечаем его занятым – удаляем из множества s.
s.erase(s.begin());
Автомобиль с
номером car только что поставили на
парковку номер ParkingPlace.
mp[car] = ParkingPlace;
} else
{
Свободных
парковочных мест нет, заносим автомобиль в очередь d.
d.push_back(car);
}
}
else
Рассмотрим
случай, когда car < 0. Автомобиль
с номером -car выезжает из парковки с
номером mp[-car]. Номер парковки, на
которой находится автомобиль с номером -car,
находим за время O(log2n)
при помощи отображения mp.
{
ParkingPlace = mp[-car];
Если имеется
очередь ждущих машин, то следует завести первую в очереди машину на только что
освободившееся место ParkingPlace.
if
(!d.empty())
{
car = d[0];
res += weight[car] * price[ParkingPlace];
mp[car] = ParkingPlace;
d.pop_front();
}
else
Если в очереди
никого нет, то просто освобождаем парковочное место ParkingPlace.
s.insert(ParkingPlace);
}
}
Выводим общую прибыль парковщика.
printf("%d\n",res);